/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***堆排序    P109                              ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
#include <ctime>
#include <cstdlib>
using std::cout;
using std::endl;
#define MAX 8000000
void heapSort(int *arr, int size);
void adjustHeap(int *arr, int i, int size);
void printArr(int *arr, int size);

void printArr(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}

void heapSort(int *arr, int size)
{
    int temp=0;
    //从最后一个非叶子节点向前遍历，调用adjustHeap函数，得到一个大顶堆
    for(int i=size/2-1;i>=0;i--){
        //相当于从后向前构建了一个大顶堆
        adjustHeap(arr,i,size);
    }
    //将大顶堆的顶点和最后一个元素进行交换
    for(int j=size-1;j>=0;j--){
        temp=arr[j];
        arr[j]=arr[0];
        arr[0]=temp;
        adjustHeap(arr,0,j);
    }
}
/*
作用：调整arr数组的前size个值，以i为顶点的大顶堆
参数：arr 数组（视为二叉树） i待调整的节点的位置  size调整的范围
返回值：void
*/
void adjustHeap(int *arr, int i, int size)
{
    int temp=arr[i];
    for(int k=2*i+1;k<size;k=2*k+1){
        if (k+1<size && arr[k+1]>arr[k]){
            k++;
        }
        if (temp<arr[k]){
            arr[i]=arr[k];
            i=k;
        }
        else{
            break;
        }
        arr[i]=temp;
    }
}

int main(int argc, char ** argv)
{
    int arr[9]={5,9,11,89,4,78,65,14,1};
    printArr(arr,9);
    heapSort(arr,9);
    printArr(arr,9);
}